#include <iostream>
#include <vector>

using namespace std;

static vector<int> prime_factorization(int n) {
    vector<int> factors;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0)
            factors.push_back(i);
        while (n % i == 0)
            n /= i;
    }
    if (n > 1)
        factors.push_back(n);
    return factors;
}

int main() {
    // Find the number with the maximum ratio of n/φ(n) for 2 ≤ n ≤ 1,000,000
#if 0
    vector<int> v {2, 3, 5, 7, 11, 13, 17, 19, 23};
    int a = 1;
    for (auto i : v) {
        a *= i;
        if (a > 1'000'000)
            break;
        cout << "a: " << a << endl;
    }
#else 
    int ans = 0;
    float max = 0;
    for (int num = 2; num <= 1'000'000; ++num) {
        vector<int> factors = prime_factorization(num);
        float phi = num;
        for (auto factor : factors)
            phi *= (1.0 - 1.0 / factor);
        float tmp = num / phi;
        if (tmp > max) {
            max = tmp;
            ans = num;
        }
    }
    cout << "Number with maximum ratio: " << ans << endl;
    cout << "Maximum ratio: " << max << endl;
#endif
}